//编写一个函数来查找字符串数组中的最长公共前缀。 
//
// 如果不存在公共前缀，返回空字符串 ""。 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["flower","flow","flight"]
//输出："fl"
// 
//
// 示例 2： 
//
// 
//输入：strs = ["dog","racecar","car"]
//输出：""
//解释：输入不存在公共前缀。 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 200 
// 0 <= strs[i].length <= 200 
// strs[i] 仅由小写英文字母组成 
// 
// Related Topics 字符串 👍 1992 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
      return "";
    }
    int min = Integer.MAX_VALUE;
    for (String str : strs) {
      min = Math.min(min, str.length());
    }
    int low = 1;
    int high = min;
    while (low <= high) {
      int middle = (low + high) / 2;
      if (this.isCommontPrefix(strs, middle)) {
        low = middle + 1;
      } else {
        high = middle - 1;
      }
    }
    return strs[0].substring(0, (low + high) / 2);
  }

  public boolean isCommontPrefix(String[] strs, int length) {
    String tmp = strs[0].substring(0, length);
    for (int i = 0; i < strs.length; i++) {
      if (!strs[i].startsWith(tmp)) {
        return false;
      }
    }
    return true;
  }
}
//leetcode submit region end(Prohibit modification and deletion)
